#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include "Vertex.h"

using namespace std;

Vertex* makeSolution() {
    Vertex* slt = new Vertex;
    for (size_t i = 0; i < 4; ++i) {
        for (size_t j = 0; j < 4; ++j) {
            slt->array[j+i*4] = j+1+i*4;
        }
    }
    slt->array[15] = 0;
    return slt;
}

Vertex* solution = makeSolution();

void freeAll(multimap<int, Vertex*>& mmap, map<long long, Vertex*>& hmap, set<long long>& closed_set, set<Vertex*>& cs) {
    for (set<Vertex*>::reverse_iterator j = cs.rbegin(); j != cs.rend(); ++j) {
        delete *j;
    }

    for (multimap<int, Vertex*>::iterator i = mmap.begin(); i != mmap.end(); ++i) {
        delete i->second;
    }

    delete solution;

    mmap.clear();
    cs.clear();
    closed_set.clear();
    hmap.clear();
}

bool relax(Vertex* v, Vertex* u) {
    if (u->g > v->g + 1) {
        u->g = v->g + 1;
        u->pred = v;
        return true;
    }
    return false;
}

bool checkSolution(Vertex* u) {
    u->setH();
    u->setHash();

    if (*u == *solution) {
        cout<<"Solution:\n";
        vector<char> path;
        ofstream output("out.txt", ofstream::out);

        while (u->pred!=NULL){
            path.push_back(u->changed);
            u=u->pred;
        }
        cout<<"Number of steps: "<<path.size()<<endl;
        output<<path.size()<<endl;

        cout<<"Steps: "<<endl;
        for (vector<char>::reverse_iterator i = path.rbegin(); i != path.rend(); ++i) {
            cout<<(short)(*i)<<" ";
            output<<(short)(*i)<<" ";
        }

        cout<<endl;
        output.close();

        return true;
    }
    return false;
}

void analyse_vertex(Vertex* v, Vertex* u, multimap<int, Vertex*>& mmap, map<long long, Vertex*>& hmap, set<long long>& closed_set) {
    if (closed_set.find(u->hash) == closed_set.end()) { // Vertex is not closed
        map<long long, Vertex*>::iterator a = hmap.find(u->hash);

        if (a != hmap.end()) {     // Vertex is already opened
            multimap<int, Vertex*>::iterator q = mmap.upper_bound(a->second->getF());
            multimap<int, Vertex*>::iterator w = mmap.lower_bound(a->second->getF());

            if (relax(v, a->second)) {
                for (; w != q; ++w){
                    if (*w->second == *a->second) {
                        mmap.erase(w);
                        break;
                    }
                }

                mmap.insert(make_pair(a->second->getF(), a->second));
            }
            delete u;
        } else {
            mmap.insert(make_pair(u->getF(), u));
            hmap.insert(make_pair(u->hash, u));
        }

    } else { delete u; }
}

bool getNextAndCheck(Vertex* v, multimap<int, Vertex*>& mmap, map<long long, Vertex*>& hmap, set<long long>& closed_set) {
    int a = 0; int b = 0;

    for (size_t i = 0; i < 4 ; ++i) {
        for (size_t j = 0; j < 4 ; ++j) {
            if (v->array[j + i*4] == 0){ a = i; b = j;}
        }
    }

    if (a < 3) {
        Vertex* u1 = new Vertex(*v);
        u1->array[b+a*4] = u1->array[b+(a+1)*4];
        u1->changed = u1->array[b+(a+1)*4];
        u1->array[b+(a+1)*4] = 0;
        u1->pred = v;
        u1->g = v->g + 1;
        if (checkSolution(u1)) return true;
        analyse_vertex(v, u1, mmap, hmap, closed_set);
    }

    if (a > 0) {
        Vertex* u2 = new Vertex(*v);
        u2->array[b+a*4] = u2->array[b+(a-1)*4];
        u2->changed = u2->array[b+(a-1)*4];
        u2->array[b+(a-1)*4] = 0;
        u2->pred = v;
        u2->g = v->g + 1;
        if (checkSolution(u2)) return true;
        analyse_vertex(v, u2, mmap, hmap, closed_set);
    }

    if (b < 3) {
        Vertex* u3 = new Vertex(*v);
        u3->array[b+a*4] = u3->array[b+1+a*4];
        u3->changed = u3->array[b+1+a*4];
        u3->array[b+1+a*4] = 0;
        u3->pred = v;
        u3->g = v->g + 1;
        if (checkSolution(u3)) return true;
        analyse_vertex(v, u3, mmap, hmap, closed_set);
    }

    if (b > 0) {
        Vertex* u4 = new Vertex(*v);
        u4->array[b+a*4] = u4->array[b-1+a*4];
        u4->changed = u4->array[b-1+a*4];
        u4->array[b-1+a*4] = 0;
        u4->pred = v;
        u4->g = v->g + 1;
        if (checkSolution(u4)) return true;
        analyse_vertex(v, u4, mmap, hmap, closed_set);
    }
    return false;
}

void readFirstVertex(Vertex* v) {
    ifstream input("in.txt", ifstream::in);
    if (!input.is_open()) { cout<<"No input file!\n"; exit(1); }

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            short n;
            input>>n;
            v->array[j + i*4] = n;
        }
    }
}

bool solutionExist(Vertex* v) {
    int N = 0;
    int i,j,e;

    for (e = 0; e < 16; ++e) {
        if (v->array[e] == 0) { break; }
    }
    bool fl;

    for (i = 1; i < 16; ++i) {
        fl = false;
        for (j = 0; j < 16; ++j) {
            if (v->array[j] == i) { fl = true; }
            if (fl && i > v->array[j] && j != e) { N++; }
        }
    }

    N += (e/4) + 1;
    if (N % 2) { return false; }

    return true;
}

int main() {
    Vertex* v1 = new Vertex;
    readFirstVertex(v1);
    v1->setH();
    v1->setHash();
    solution->setHash();
    solution->setH();

    cout<<"Input:"<<endl;
    v1->print();

    if (*v1 == *solution) {
        cout<<"Nothing to do here!\n";
        system("pause");
        exit(0);
    }

    if (!solutionExist(v1)){
        cout<<"No solution!"<<endl;
        system("pause");
        exit(0);
    }

    multimap<int, Vertex*> mmap;
    map<long long, Vertex*> hmap;
    set<long long> closed_set;
    set<Vertex*> closed_setV;

    mmap.insert(make_pair(v1->getF(), v1));
    hmap.insert(make_pair(v1->hash, v1));

    Vertex* u;
    while (!mmap.empty()) {
        u = mmap.begin()->second;

        closed_set.insert(u->hash);
        closed_setV.insert(u);

        mmap.erase(mmap.begin());
        hmap.erase(hmap.find(u->hash));

        if (getNextAndCheck(u, mmap, hmap, closed_set)) break;
    }

    freeAll(mmap, hmap, closed_set, closed_setV);

    system("pause");
    return 0;
}
